package cn.edu.leetcode.动态规划;

public class 跳跃游戏2 {
    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};

        System.out.println(jump(nums));
    }

    public static int jump(int[] nums) {
        int[] jumpnum = new int[nums.length];

        jumpnum[0] = 0;
        for (int i = 0; i < jumpnum.length; i++) {
            for (int j = 1; j <= nums[i] && i+j<jumpnum.length; j++) {
                if (jumpnum[i+j] == 0) jumpnum[i+j] = jumpnum[i]+1;
                jumpnum[i+j] = Math.min(jumpnum[i+j], jumpnum[i]+1);
            }
        }

        return jumpnum[jumpnum.length-1];
    }
}
